#region

using Common.DataStructures.Heap;

#endregion

namespace AdvancedTraining.Lesson52;

/// <summary>
/// 避免洪水泛滥问题 - LeetCode 1488
/// 使用贪心算法和优先队列安排抽水顺序，避免湖泊洪水泛滥
/// </summary>
public class AvoidFloodInTheCity //leetcode_1488
{
    /// <summary>
    /// 计算避免洪水泛滥的抽水安排
    /// 算法思路：贪心 + 优先队列
    /// 1. 记录每个湖泊的下雨日期
    /// 2. 使用集合记录已满的湖泊
    /// 3. 使用最小堆记录需要优先抽水的湖泊（按下次下雨时间排序）
    /// 4. 在晴天时，优先抽干最早会下雨的湖泊
    /// 时间复杂度：O(N log N)，其中N为天数
    /// 空间复杂度：O(N)
    /// </summary>
    /// <param name="rains">降雨数组，rains[i]表示第i天降雨的湖泊编号，0表示晴天</param>
    /// <returns>抽水安排数组，-1表示下雨天，其他数字表示抽水的湖泊编号</returns>
    public static int[] AvoidFlood(int[] rains)
    {
        var n = rains.Length;
        var ans = new int[n];
        var invalid = Array.Empty<int>();
        // key : 某个湖
        // value : 这个湖在哪些位置降雨
        // 4 : {3,7,19,21}
        // 1 : { 13 }
        // 2 : {4, 56}
        var map = new Dictionary<int, LinkedList<int>>();
        for (var i = 0; i < n; i++)
            if (rains[i] != 0)
            {
                // 第i天要下雨，rains[i]
                // 3天 9号
                // 9号 { 3 }
                // 9号 {1, 3}
                if (!map.ContainsKey(rains[i])) map[rains[i]] = new LinkedList<int>();
                map[rains[i]].AddLast(i);
            }

        // 没抽干的湖泊表
        // 某个湖如果满了，加入到set里
        // 某个湖被抽干了，从set中移除
        var set = new HashSet<int>();
        // 这个堆的堆顶表示最先处理的湖是哪个
        Heap<Work> minHeap = new((x, y) => x.NextRain - y.NextRain);
        for (var i = 0; i < n; i++)
            // 0 1 2 3 ...
            if (rains[i] != 0)
            {
                if (!set.Add(rains[i])) return invalid;
                // 放入到没抽干的表里
                map[rains[i]].RemoveFirst();
                if (map[rains[i]].Count > 0) minHeap.Push(new Work(rains[i], map[rains[i]].First()));
                // 题目规定
                ans[i] = -1;
            }
            else
            {
                // 今天干活！
                if (minHeap.isEmpty)
                {
                    ans[i] = 1;
                }
                else
                {
                    var cur = minHeap.Pop();
                    set.Remove(cur.Lake);
                    ans[i] = cur.Lake;
                }
            }

        return ans;
    }

    /// <summary>
    /// 工作任务类，用于优先队列
    /// 表示哪个湖泊需要在什么时候抽水
    /// </summary>
    public class Work(int l, int p) : IComparable<Work>
    {
        public readonly int Lake = l;
        public readonly int NextRain = p;

        public int CompareTo(Work? o)
        {
            if (o == null) return 1;
            return NextRain - o.NextRain;
        }
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 避免洪水泛滥问题测试 ===");

        // 测试用例1: LeetCode官方示例1
        Test1();

        // 测试用例2: LeetCode官方示例2
        Test2();

        // 测试用例3: 无晴天情况
        Test3();

        // 测试用例4: 全晴天情况
        Test4();

        // 测试用例5: 复杂情况
        Test5();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("贪心策略：晴天时优先抽干最早会再次下雨的湖泊");
        Console.WriteLine("优先队列：按下次下雨时间排序，确保最优选择");
        Console.WriteLine("哈希表：记录每个湖泊的下雨日期，方便快速查找");
        Console.WriteLine("集合：记录当前已满的湖泊，检测洪水风险");
        Console.WriteLine("时间复杂度：O(N log N)，空间复杂度：O(N)");
    }

    /// <summary>
    /// 测试用例1: LeetCode官方示例1
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: LeetCode官方示例1");
        int[] rains = [1, 2, 0, 0, 2, 1];
        var result = AvoidFlood(rains);
        Console.WriteLine($"降雨安排: [{string.Join(", ", rains)}]");
        Console.WriteLine($"抽水安排: [{string.Join(", ", result)}]");
        Console.WriteLine($"结果有效: {result.Length > 0} (期望: 有效)");
    }

    /// <summary>
    /// 测试用例2: LeetCode官方示例2
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: LeetCode官方示例2");
        int[] rains = [1, 2, 0, 1, 2];
        var result = AvoidFlood(rains);
        Console.WriteLine($"降雨安排: [{string.Join(", ", rains)}]");
        Console.WriteLine($"抽水安排: [{string.Join(", ", result)}]");
        Console.WriteLine($"结果有效: {result.Length > 0} (期望: 有效)");
    }

    /// <summary>
    /// 测试用例3: 无晴天情况
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 无晴天情况");
        int[] rains = [1, 2, 3, 1, 2];
        var result = AvoidFlood(rains);
        Console.WriteLine($"降雨安排: [{string.Join(", ", rains)}]");
        Console.WriteLine($"抽水安排: [{string.Join(", ", result)}]");
        Console.WriteLine($"结果有效: {result.Length > 0} (期望: 无效，无法避免洪水)");
    }

    /// <summary>
    /// 测试用例4: 全晴天情况
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 全晴天情况");
        int[] rains = [0, 0, 0, 0, 0];
        var result = AvoidFlood(rains);
        Console.WriteLine($"降雨安排: [{string.Join(", ", rains)}]");
        Console.WriteLine($"抽水安排: [{string.Join(", ", result)}]");
        Console.WriteLine($"结果有效: {result.Length > 0} (期望: 有效，全部抽1号湖)");
    }

    /// <summary>
    /// 测试用例5: 复杂情况
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 复杂情况");
        int[] rains = [1, 0, 2, 0, 3, 0, 1, 0, 2];
        var result = AvoidFlood(rains);
        Console.WriteLine($"降雨安排: [{string.Join(", ", rains)}]");
        Console.WriteLine($"抽水安排: [{string.Join(", ", result)}]");
        Console.WriteLine($"结果有效: {result.Length > 0} (期望: 有效)");
        if (result.Length > 0)
        {
            Console.WriteLine("抽水策略分析:");
            for (var i = 0; i < result.Length; i++)
            {
                if (rains[i] == 0)
                    Console.WriteLine($"第{i}天: 晴天，抽{result[i]}号湖的水");
                else if (result[i] == -1)
                    Console.WriteLine($"第{i}天: 雨天，{rains[i]}号湖下雨");
            }
        }
    }
}